package UnitTest;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @Auther: arcadia
 * @Date: 20-2-16 15 11
 * @Description: leetcode 40
 */
public class CombinationSum2 {

    public static void main(String[] args) {
        int[] candidations = {10,1,2,7,6,1,5};
        int target = 8;
        CombinationSum2 combinationSum2 = new CombinationSum2();
        List<List<Integer>> lists = combinationSum2.combinationSum(candidations, target);
        System.out.println(lists);

    }

    private List<List<Integer>> combinationSum(int[] combinations,int target){
        List<List<Integer>> res = new ArrayList<>();
        Arrays.sort(combinations);
        helper(combinations,target,0,new ArrayList<>(),res);
        return res;
    }

    private void helper(int[] combinations, int target, int index, List<Integer> temp,List<List<Integer>> res ) {
        if (target<=0){
            if (target==0){
                res.add(new ArrayList<>(temp));
            }
        }
        for (int i = index;i<combinations.length;i++) {
            if (index < i && combinations[i] == combinations[i - 1]) {
                continue;
            }
            temp.add(combinations[i]);
            helper(combinations, target - combinations[i], index + 1, temp, res);
            temp.remove(temp.size() - 1);
        }
    }
}
